#include <iostream>
using namespace std;

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

class solution
{
    ListNode* reverseBetween(ListNode* head, int m, int n)
    {
        // 判断是否为空
        if (!head)
            return nullptr;
        // 不为空, 创造两个指针primary, reverse分别指向反转范围内外的节点
        ListNode* primary = nullptr, *reverse = nullptr;
        int count = 1;
        listNode* cur = head, *tail = primary; // 进行遍历的指针
        while(cur != nullptr)
        {
            if (count >= m && count <= n)
            {
                // 现在指向的节点需要头插到reverse
                if(!reverse)
                {
                    // reverse == nullptr
                    reverse = cur;
                    cur = cur->next;
                    reverse->next = nullptr;
                }
                else
                {
                    listNode* next = cur->next;
                    cur->next = reverse;
                    reverse = cur;
                    cur = next;
                }
            }
            else
            {
                // 指向的节点需要尾插到primary
                if (!tail)
                {
                    // tail == primary
                    tail = cur;
                    cur = cur->next;
                    tail->next = nullptr;
                }
                else
                {
                    
                    listNode* next = cur->next;
                    tail->next = cur;
                    cur = next;
                    tail = tail->next;
                    tail->next = nullptr;
                }
            }
            ++count;
        }
        // 插完了, 现在开始拼接
        cur = primary;
        count = 1;
        while (count <= m - 1)
        {
            cur = cur->next;
        }
        tail = reverse;
        if (!tail)
            return primary;
        else
        {
            while (tail->next != nullptr)
                tail = tail->next;
            tail->next = cur->next;
            cur->next = reverse;
            head = primary;
            return head;
        }
    }
};
